package com.lims.algorithm.algset.tree;

import java.util.Arrays;

/**
 * <功能简述> 重建二叉树
 *
 * @author: lims
 * @create: 2019-04-22 14:20
 */
public class ConstructTree {
    /*static class BinaryTreeNode {
        public int data;
        public BinaryTreeNode left;
        public BinaryTreeNode right;

        public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right){
            super();
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public BinaryTreeNode(int data){
            this.data = data;
        }
    }*/

    /**
     * 重建二叉树
     *
     * @param preOrder
     * @param inOrder
     * @return
     */
    public static BinaryTree.BinaryTreeNode reConstruct(int[] preOrder, int[] inOrder) {
        if (preOrder == null || inOrder == null) {
            return null;
        }

        //找到根节点
        int rootData = preOrder[0];
        BinaryTree.BinaryTreeNode root = new BinaryTree.BinaryTreeNode(rootData);
        root.left = root.right = null;

        //判断仅有一个节点的情况 也是递归的终止条件
        if (preOrder.length == 1 && inOrder.length == 1) {
            if (preOrder[0] == inOrder[0]) {
                return root;
            } else {
                throw new IllegalArgumentException("invalid input");
            }
        }

        //从中序遍历结果中找出根节点下标索引
        int rootIndex = 0;
        while (rootIndex < inOrder.length && inOrder[rootIndex] != rootData) {
            rootIndex++;
        }

        //递归构造左子树
        if (rootIndex > 0) {
            root.left = reConstruct(
                    Arrays.copyOfRange(preOrder, 1, rootIndex + 1),
                    Arrays.copyOfRange(inOrder, 0, rootIndex)
            );
        }
        //递归构造右子树
        if (rootIndex < inOrder.length - 1) {
            root.right = reConstruct(
                    Arrays.copyOfRange(preOrder, rootIndex + 1, preOrder.length),
                    Arrays.copyOfRange(inOrder, rootIndex + 1, inOrder.length)
            );
        }

        return root;
    }


    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};

        BinaryTree.BinaryTreeNode root = reConstruct(pre, in);
        BinaryTree.postOrderSingleStack(root);
    }
}
